//
// Created by LiuYou on 2021/12/2.
//

#include <iostream>
#include <random>
#include <iterator>


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


static std::vector<int> partition(std::vector<int>& arr, int left, int right) {
    int leftSide = left - 1;
    // todo 笔记: 我终于知道这里为什么右侧 > 区域的左边界是 right了。因为 right现在存储的是 划分值。
    //  最后是一定会交换的。
    int rightSide = right;
    int pivot = arr[right];
    int index = left;

    while (index < rightSide) {
        if (arr[index] < pivot) {
            std::swap( arr[index++], arr[++leftSide] );
        } else if (arr[index] == pivot) {
            ++index;
        } else {
            std::swap( arr[index], arr[--rightSide] );
        }
    }

    std::swap( arr[index], arr[right] );

    return std::vector<int>{leftSide + 1, rightSide};
}


static void quickSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int random = randomNumberFromTheRange( left, right );
        std::swap( arr[random], arr[right] );

        // todo 笔记: 下面这两句都是可以的！因为对 partitionRegionRange对象 我仅仅是只读,
        //  所以使用 const std::vector<int>& 类型来接受返回值可以避免一次构造与析构, 提高效率。
        const std::vector<int>& partitionRegionRange = partition( arr, left, right );
//        std::vector<int> partitionRegionRange = partition( arr, left, right );

        quickSort( arr, left, partitionRegionRange[0] - 1 );
        quickSort( arr, partitionRegionRange[1] + 1, right );

    } else {
        return;
    }
}


static void quickSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    quickSort( arr, 0, arr.size() - 1 );
}


int main(int argc, char** argv) {
    std::vector<int> arr;
    arr.reserve( 10 );
    for (int i = 0; i < 10; ++i) {
        arr.push_back( randomNumberFromTheRange( 0, 100 ));
    }
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    quickSort( arr );
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}
